// 文件名：priority_queue_merge_k_sorted.cpp
// 目的：合并 k 个有序数组为一个有序序列，使用最小堆实现多路归并。
// 思路：
//   - 堆中元素 Entry 记录当前值、来自的数组下标 arrayIndex、数组内的元素下标 elementIndex；
//   - 初始化：每个非空数组压入其首元素到最小堆；
//   - 循环：每次弹出堆顶最小值加入结果，并将其所在数组的下一个元素压入堆；
//   - 堆为空时结束，得到全局有序结果。
// 复杂度：
//   - 时间：O(T log k)，T 为总元素数；空间：O(k) 堆大小。
// 注意：
//   - 比较器 EntryCompare 令 priority_queue 作为“最小堆”。

#include <iostream>
#include <queue>
#include <vector>

struct Entry {
    int value;
    std::size_t arrayIndex;
    std::size_t elementIndex;
};

struct EntryCompare {
    bool operator()(const Entry& a, const Entry& b) const noexcept {
        return a.value > b.value; // 最小堆
    }
};

std::vector<int> mergeSorted(const std::vector<std::vector<int>>& arrays) {
    std::priority_queue<Entry, std::vector<Entry>, EntryCompare> heap;
    std::vector<int> result;

    // 初始化：将每个数组的首元素入堆
    for (std::size_t i = 0; i < arrays.size(); ++i) {
        if (!arrays[i].empty()) {
            heap.push(Entry{arrays[i][0], i, 0});
        }
    }

    // 多路归并
    while (!heap.empty()) {
        auto entry = heap.top();
        heap.pop();
        result.push_back(entry.value);

        if (entry.elementIndex + 1 < arrays[entry.arrayIndex].size()) {
            std::size_t nextIndex = entry.elementIndex + 1;
            heap.push(Entry{
                arrays[entry.arrayIndex][nextIndex],
                entry.arrayIndex,
                nextIndex
            });
        }
    }
    return result;
}

int main() {
    std::vector<std::vector<int>> arrays = {
        {1, 4, 9},
        {2, 3, 8},
        {0, 5, 7, 10}
    };

    auto merged = mergeSorted(arrays);
    std::cout << "Merged sequence: ";
    for (int v : merged) {
        std::cout << v << ' ';
    }
    std::cout << '\n';

    return 0;
}